1. Field of the Invention
The present invention relates to an improved adaptive binary arithmetic coder that provides improved processing speed and accuracy over conventional arithmetic coders.
2. Related Art
Arithmetic coders provide well-known algorithms for encoding data. Compression ratios of the arithmetic coders can reach the information theory limit. The arithmetic coder and decoder must possess good estimates of the probability distribution of each symbol to code. For each symbol to be coded in a string element, the encoder and decoder must possess a table containing estimated probabilities for the occurrence of each possible symbol at each point in the symbol string. The coders themselves must perform a table search and at least one multiplication. For this reason, arithmetic coders incur high computational expense. Binary adaptive arithmetic coders, such as the "Q-Coder," by Pennebaker, et al. (1998) and the "QM-Coder," by Ono (1993), have been developed to overcome this drawback.
A high-level system diagram of a prior art binary arithmetic coder is shown in FIG. 1. Data to be coded is input to an encoder 100. The encoder 100 encodes the data and outputs a string of coded data to a channel 200. A decoder 300 retrieves the code string from the channel 200 and replicates the original data by decoding the coded data.
The coding process often is described by the operation of the decoder 300. In the decoder, the code string is interpreted as a binary representation of a real number contained in the unit interval [0,1[. The binary arithmetic coder divides the unit interval into two sub-intervals having lengths that are proportional to the estimated probabilities of each value of the first bit in the symbol string. Any code string located in a first, lower sub-interval represents a symbol string starting with a zero (0). Conversely, any code string located in the upper sub-interval represents a symbol string starting with a one (1).
Each of the sub-intervals can be divided into two smaller sub-intervals having lengths that are proportional to the estimated conditional probabilities of the second symbol bit given the previously encoded symbol bit. Any code string located in one of these sub-intervals represents a symbol string starting with the corresponding two bit prefix.
The decoding process is repeated. Sub-intervals are themselves divided into smaller sub-intervals representing probabilities of the value of the next bit in the symbol string. The process produces a partition of the unit interval having sub-intervals that correspond to each possible value of the symbol string. Any code string in the interval can be chosen corresponding to the encoded symbol string.
According to theory, when an interval is divided into sub-intervals, the length of each sub-interval should be proportional to the probability of the value of the next data symbol to be decoded given the previous symbol bits. The probability distribution of the code string therefore would be uniform in the interval. Since each code bit is equally likely to be a 0 or a 1, it would carry as much information as information theory allows. In other words, the coder would achieve entropic compression.
The known Q-Coder and QM-Coder, while they represent advances over traditional arithmetic coders, do not provide performance that approaches entropic compression. Thus, there is a need in the art for a binary arithmetic coder that provides improved compression ratios than the Q-Code and the QM-Coder.
Decoding speed is an important performance characteristic of data coding systems. Decoding latency, the time that is required to generate decoded data once the coded data is received should be minimized wherever possible. Thus, decoders that introduce lengthy or complex computational processes to the decoding operation are disfavored. Accordingly, there is a need in the art for a data decoding scheme that is computationally simple and provides improved throughput of decoded data.